﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TooWhite.Graph
{
    public class AdjacencyList<T> where T : IEquatable<T>
    {
        /// <summary>
        /// 存放所有顶点的表
        /// </summary>
        List<Vertex> _vertexList = new List<Vertex>();

        /// <summary>
        /// 顶点类型定义
        /// </summary>
        public class Vertex
        {
            public T Data;
            public Edge FirstEdge;
            public bool Visited;
            public Vertex(T data)
            {
                Data = data;
                Visited = false;
                FirstEdge = null;
            }
            public List<Vertex> GetAdjacentVetexes()
            {
                List<Vertex> rst = new List<Vertex>();
                Edge p = this.FirstEdge;
                while(p != null)
                {
                    rst.Add(p.AdjacentVertex);
                    p = p.NextNode;
                }
                return rst;
            }
        }

        /// <summary>
        /// 边类型定义
        /// </summary>
        public class Edge
        {
            /// <summary>
            /// 目标顶点引用
            /// </summary>
            public Vertex AdjacentVertex;
            /// <summary>
            /// 下一条边
            /// </summary>
            public Edge NextNode;
            /// <summary>
            /// 权重，HasWeight为真时有效
            /// </summary>
            public double Weight
            {
                set;
                get;
            }
            /// <summary>
            /// 是否为带权边
            /// </summary>
            public bool HasWeight;
            /// <summary>
            /// 带权边构造函数
            /// </summary>
            /// <param name="weight">权值</param>
            /// <param name="vertex">目标顶点</param>
            public Edge(double weight, Vertex vertex)
            {
                HasWeight = true;
                Weight = weight;
                AdjacentVertex = vertex;
                NextNode = null;
            }
            /// <summary>
            /// 无权边构造函数
            /// </summary>
            /// <param name="vertex">目标顶点</param>
            public Edge(Vertex vertex)
            {
                HasWeight = false;
                AdjacentVertex = vertex;
                NextNode = null;
            }
        }

        /// <summary>
        /// 根据数据得到顶点引用
        /// </summary>
        /// <param name="data">数据</param>
        /// <returns>节点引用</returns>
        public Vertex GetVertex(T data)
        {
            foreach(Vertex it in _vertexList)
                if(it.Data.Equals(data)) return it;
            throw new Exception("找不到含有这个内容的结点。");
        }

        /// <summary>
        /// 根据数据取得顶点
        /// </summary>
        /// <param name="data">数据内容</param>
        /// <returns>顶点引用</returns>
        public Vertex this[T data]
        {
            get
            {
                return GetVertex(data);
            }
        }

        /// <summary>
        /// 添加一个顶点
        /// </summary>
        /// <param name="data">数据</param>
        /// <returns>得到的节点引用</returns>
        public Vertex AddVertex(T data)
        {
            Vertex vertex = new Vertex(data);
            _vertexList.Add(vertex);
            return vertex;
        }

        /// <summary>
        /// 测试用方法，输出接点数据到控制台
        /// </summary>
        /// <param name="v"></param>
        public static void OutputOnConsole(Vertex v)
        {
            Console.Write("{0,4}", v.Data);
        }

        #region 添加边
        public void AddEdge(Vertex from, Vertex to, bool direction = false)
        {
            Edge temp = from.FirstEdge;
            from.FirstEdge = new Edge(to);
            from.FirstEdge.NextNode = temp;
            if(!direction)
            {
                temp = to.FirstEdge;
                to.FirstEdge = new Edge(from);
                to.FirstEdge.NextNode = temp;
            }
        }

        public void AddEdge(Vertex from, Vertex to, double weight, bool direction = false)
        {
            Edge temp = from.FirstEdge;
            from.FirstEdge = new Edge(weight, to);
            from.FirstEdge.NextNode = temp;
            if(!direction)
            {
                temp = to.FirstEdge;
                to.FirstEdge = new Edge(weight, from);
                to.FirstEdge.NextNode = temp;
            }
        }

        public void AddEdge(T from, T to, bool direction = false)
        {
            Vertex vFrom = GetVertex(from);
            Vertex vTo = GetVertex(to);
            AddEdge(vFrom, vTo, direction);
        }

        public void AddEdge(T from, T to, double weight, bool direction = false)
        {
            Vertex vFrom = GetVertex(from);
            Vertex vTo = GetVertex(to);
            AddEdge(vFrom, vTo, weight, direction);
        }
        #endregion      

        #region 得到邻接顶点
        public List<Vertex> GetAdjacentVetexes(Vertex vertex)
        {
            List<Vertex> rst = new List<Vertex>();
            Edge p = vertex.FirstEdge;
            while(p != null)
            {
                rst.Add(p.AdjacentVertex);
                p = p.NextNode;
            }
            return rst;
        }

        public List<Vertex> GetAdjacentVetexes(T data)
        {
            Vertex v = GetVertex(data);
            return GetAdjacentVetexes(v);
        }
        #endregion

        #region 深度优先遍历
        void _DFS(Vertex startVertex, Action<Vertex> visit)
        {

            visit(startVertex);
            startVertex.Visited = true;
            List<Vertex> adj = GetAdjacentVetexes(startVertex);
            foreach(Vertex it in adj)
            {
                if(it.Visited == false)
                    _DFS(it, visit);
            }
        }

        public void DFS(Vertex startVertex, Action<Vertex> visit)
        {
            foreach(Vertex it in _vertexList) it.Visited = false;
            _DFS(startVertex, visit);
        }

        public void DFS(T start, Action<Vertex> visit)
        {
            Vertex vStart = GetVertex(start);
            DFS(vStart, visit);
        }
        #endregion

        #region 广度优先遍历
        public void BFS(Vertex startVertex, Action<Vertex> visit)
        {
            foreach(Vertex it in _vertexList) it.Visited = false;
            Vertex v = startVertex;
            Queue<Vertex> q = new Queue<Vertex>();
            q.Enqueue(v);
            while(q.Count != 0)
            {
                Vertex now = q.Dequeue();
                if(now.Visited == false)
                    visit(now);
                else continue;
                now.Visited = true;
                List<Vertex> adj = GetAdjacentVetexes(now);
                while(adj.Count != 0)
                {
                    if(adj[0].Visited == false)
                        q.Enqueue(adj[0]);
                    adj.Remove(adj[0]);
                }
            }
        }

        public void BFS(T start, Action<Vertex> visit)
        {
            Vertex vStart = GetVertex(start);
            BFS(vStart, visit);
        }

        #endregion

        #region 删除顶点
        public void DeleteVertex(Vertex vertex)
        {
            foreach(Vertex it in _vertexList)
            {
                DeleteEdge(it, vertex);
            }

            _vertexList.Remove(vertex);
        }

        public void DeleteVertex(T data)
        {
            DeleteVertex(this[data]);
        }
        #endregion

        #region 删除边
        public void DeleteEdge(Vertex from, Vertex to, bool direction = false)
        {
            if(from.FirstEdge == null) throw new Exception("参数顶点没有任何邻接的顶点。");
            Edge head = new Edge(null);
            Edge p = from.FirstEdge;
            head.NextNode = p;
            Edge pre = head;
            while(p != null)
            {
                if(p.AdjacentVertex == to)
                {
                    pre.NextNode = p.NextNode;
                    p = p.NextNode;
                    continue;
                }
                else
                {
                    pre = p;
                    p = p.NextNode;
                }
            }

            from.FirstEdge = head.NextNode;

            if(!direction) DeleteEdge(to, from, true);
        }

        public void DeleteEdge(T from, T to, bool direction = false)
        {
            DeleteEdge(this[from], this[to], direction);
        }
        #endregion
    }
}
